package vineet.java.code.tree;

public class BinaryTree
{
	private Node root ;
	
	public BinaryTree(int value)
	{
		this.root = new Node(value) ;
		this.root.setLeft(null);
		this.root.setRight(null);
	}
	
	public Node getRoot() {
		return root;
	}

	private void preOrder(Node parent)
	{
		if(parent!=null)
		{
			System.out.print(parent.getData()+"=> ");
			preOrder(parent.getLeft());
			preOrder(parent.getRight());
		}
	}
	private void postOrder(Node parent)
	{
		if(parent!=null)
		{
		    postOrder(parent.getLeft());
		    postOrder(parent.getRight());
			System.out.print(parent.getData()+"=> ");
		}
	}
	private void inOrder(Node parent)
	{
		if(parent!=null)
		{
		    inOrder(parent.getLeft());
			System.out.print(parent.getData()+"=> ");
			inOrder(parent.getRight());
		}
	}
	//To move a non-leaf node down in the tree, we either swap it with the smallest key in the right subtree or with the largest one in the left subtree. 
	private void remove(int value,Node parent)
	{
		
	}
	public void remove(int value)
	{
		
	}
	
	public Node search(int value)
	{
		Node tmp = this.root;
		while(tmp != null)
		{
			if(value < tmp.getData())
			{
				tmp = tmp.getLeft();
			}
			else if(value > tmp.getData())
			{
				tmp = tmp.getRight();
		    }
			else
			{
				return tmp;
			}
		}
		return tmp;
	}
	public Node findSmallest()
	{
		Node tmp = this.root ;
		if(tmp != null)
		{
			while(tmp.getLeft()!= null)
			{
				tmp = tmp.getLeft();
			}
		}
		
		return tmp;
	}
	public Node findSmallest(Node parent)
	{
		Node tmp = parent ;
		if(tmp != null)
		{
			while(tmp.getLeft()!= null)
			{
				tmp = tmp.getLeft();
			}
		}
		
		return tmp;
	}
	public Node findLargest()
	{
		Node tmp = this.root ;
		if(tmp != null)
		{
			while(tmp.getRight()!=null)
			{
				tmp = tmp.getRight();
			}
		}
		return tmp;
	}
	public Node findLargest(Node parent)
	{
		Node tmp = parent;
		if(tmp != null)
		{
			while(tmp.getRight()!=null)
			{
				tmp = tmp.getRight();
			}
		}
		return tmp;
	}
	private int height(Node parent)
	{
		if(parent == null)
		{
			return -1;
		}
		else if(parent.getLeft() == null && parent.getRight() == null)
		{
			return 0;
		}
		else
		{
			int hleft = height(parent.getLeft());
			int hright = height(parent.getRight());
			return (hleft > hright ? hleft : hright) + 1;
		}
	}
	
	public int height()
	{
		return height(this.root);
	}
	private void insert(int value,Node parent)
	{
		if(value < parent.getData())
		{
			if(parent.getLeft() != null)
			{
				insert(value,parent.getLeft());
			}
			else
			{
				Node tmp = new Node(value);
				tmp.setLeft(null);
				tmp.setRight(null);
				parent.setLeft(tmp);
			}
		}
		else if(parent.getData() < value)
		{
			if(parent.getRight() != null)
			{
				insert(value, parent.getRight());
			}
			else
			{
				Node tmp = new Node(value);
				tmp.setLeft(null);
				tmp.setRight(null);
				parent.setRight(tmp);
			}
		}
	}

	public void insert(int value){
	    this.insert(value, this.root);
	}

	public void preOrder(){
	    this.preOrder(this.root);
	}
	public void postOrder(){
        this.postOrder(this.root);
    }
	public void inOrder(){
        this.inOrder(this.root);
    }
}
